#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <SeqQueue.h>
#include "stack_link.h"
#include "tree.h"

/* 结点插入 */
int tree_insert(tree_st **ptr,datatype data)
{
		tree_st *newnode = NULL;
		if (*ptr == NULL)
		{
				newnode = malloc(sizeof(*newnode));
				if(newnode == NULL)
				{
					fprintf(stderr,"malloc() failed!\n");
					exit(1);
				}
				newnode->data = data;
				newnode->lchild = NULL;
				newnode->rchild = NULL;

				*ptr = newnode;
				return 0;
		}
		if (data <= (*ptr)->data)
		{
			tree_insert(&(*ptr)->lchild,data);
		}
		else
		{
			tree_insert(&(*ptr)->rchild,data);
		}
}

/* 结点查找 */
tree_st *tree_find(tree_st *ptr,datatype data)
{
		if (ptr == NULL)
			return NULL;
		if (ptr->data == data)
			return ptr;
		if (data < ptr->data)
		{
			tree_find(ptr->lchild,data);
		}
		else
		{
			tree_find(ptr->rchild,data);
		}
}

/* 画树 */
static void draw(tree_st *ptr,int level)
{
	if (ptr == NULL)
		return ;
	draw(ptr->rchild,level+1);
	int i;
	for (i = 0; i < level; i++)
	{
		printf("\t");
	}
	printf("%c\n",ptr->data);
	draw(ptr->lchild,level+1);
}

void tree_draw(tree_st *ptr)
{
	draw(ptr,0);
}

/* 获取树结点的个数 */
static int get_num(tree_st *ptr)
{
	if (ptr == NULL)
		return 0;
	return get_num(ptr->lchild) + get_num(ptr->rchild) + 1;
}

/* 树的深度 */
int getDepth(tree_st *ptr)
{
	if (ptr == NULL)
	{
		return 0;
	}

	return getDepth(ptr->lchild) > getDepth(ptr->rchild) ? (getDepth(ptr->lchild) + 1) : (getDepth(ptr->rchild) + 1);
}

/* 找树的最小结点 */
static tree_st *find_min(tree_st *ptr)
{
	if (ptr->lchild == NULL)
		return ptr;
	find_min(ptr->lchild);
}

/* 左旋 */
static void left(tree_st **ptr)
{
	tree_st *cur = *ptr;
	*ptr = cur->rchild;
	cur->rchild = NULL;
	find_min(*ptr)->lchild = cur;
}

/* 找树的最大结点 */
static tree_st *find_max(tree_st *ptr)
{
	if (ptr->rchild == NULL)
		return ptr;
	find_max(ptr->rchild);
}

/* 右旋 */
static void right(tree_st **ptr)
{
	tree_st *cur = *ptr;
	*ptr = cur->lchild;
	cur->lchild = NULL;
	find_max(*ptr)->rchild = cur;
}

/* 平衡树 */
void tree_balance(tree_st **ptr)
{
	if (*ptr == NULL)
		return ;
	while(1)
	{
		int sub;
		sub = get_num((*ptr)->lchild) - get_num((*ptr)->rchild);
		if (sub <= 1 && sub >= -1)
			break;
		if (sub > 1)
		{
			right(ptr);
		}
		else
		{
			left(ptr);
		}
	}
	tree_balance(&(*ptr)->lchild);
	tree_balance(&(*ptr)->rchild);	
}

/* 树节点删除 */
void tree_delete(tree_st **ptr,datatype data)
{
	tree_st **node = ptr;
	tree_st *cur = NULL;
	while (*node != NULL && (*node)->data != data)
	{
		if ((*node)->data > data)
		{
			node = &(*node)->lchild;
		}
		else
		{
			node = &(*node)->rchild;
		}
	}
	//node保存的是上一个结点的指针
	if (*node == NULL)
	{
		return ;
	}
	cur = *node;
	if (cur->rchild == NULL)
	{
		*node = cur->lchild;	
	}
	else
	{
		*node = cur->rchild;
		find_min(cur->rchild)->lchild = cur->lchild;
	}
	free(cur);
}

/* 层次遍历 */
void level_show(tree_st *ptr)
{
	queue_head *que = NULL;
	que = Init_Queue();
	
	Datatype data;
	EnQueue(que,ptr->data);
	while (!IsEmpty_Queue(que))
	{
		tree_st *cur = NULL;
		DeQueue(que,&data);
		printf("%c ",data);
		
		/* 找到为data的结点位置 */	
		cur = tree_find(ptr,data);
		if(cur->lchild)
			EnQueue(que,cur->lchild->data);
		if(cur->rchild)
			EnQueue(que,cur->rchild->data);
	}		
}

/* 先序遍历 */
void first_show(tree_st *ptr)
{
	if (ptr == NULL)
		return ;
	printf("%c ",ptr->data);
	first_show(ptr->lchild);
	first_show(ptr->rchild);
}

/* 中序遍历 */
void middle_show(tree_st *ptr)
{
	if (ptr == NULL)
		return ;
	middle_show(ptr->lchild);
	printf("%c ",ptr->data);
	middle_show(ptr->rchild);
}

/* 后序遍历 */
void last_show(tree_st *ptr)
{
	if (ptr == NULL)
		return ;
	last_show(ptr->lchild);
	last_show(ptr->rchild);
	printf("%c ",ptr->data);
}

/* 非递归版先序遍历
 * 可转为指针入栈，栈元素类型转为void *
 *
 *  */
void firstShow(tree_st *tree)
{
	tree_st *ptr = tree;
	link_head *stack = NULL;
	tree_st *cur = NULL;
	Init_Stack(&stack);
	Datatype data;
	tree_draw(tree);

	while (ptr || (IsEmpty_Stack(stack) == 0))
	{
		if (ptr)
		{
			/* 先序遍历 */
//			printf("%c ",ptr->data);
			Push_Stack(stack,ptr->data);
			ptr = ptr->lchild;
		}
		else
		{
			Pop_Stack(stack,&data);	
			/* 中序遍历 */
			printf("%c ",data);
			cur = tree_find(tree,data);
			if (cur->rchild)
				ptr = cur->rchild;
			else
				ptr = NULL;
		}
	}

}
